import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86136
 * Date: 2024-10-12
 * Time: 18:16
 */
class IntCompare implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);//this.val - o.val-->大根堆，系统默认为小跟堆
    }
}
public class Test {
    //top-k问题
    public static int[] smallestK(int[] arr, int k) {
        int[] smallest = new int[k];
        if(arr == null || k == 0) {
            return smallest;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k,new IntCompare());
        //K*logK
        for(int i = 0;i < k;i++) {
            priorityQueue.offer(arr[i]);
        }
        //(n-K)*logK
        for(int i = k;i < arr.length;i++) {
            if(priorityQueue.peek() > arr[i]) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for(int i = 0; i < k;i++) {
            smallest[i] = priorityQueue.poll();
        }
        return smallest;
    }

    public static void main(String[] args) {
        int[] arr = {1,3,5,7,2,4,6,8};
        int[] ret = smallestK(arr,3);
    }
    public static void main1(String[] args) {
        //Queue<Integer> queue1 = new PriorityQueue<>(); //使用接口实现
        PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(2);
        priorityQueue1.offer(21);
        priorityQueue1.offer(22);
        System.out.println(priorityQueue1.peek());//22 大根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCompare());
        priorityQueue.offer(11);
        priorityQueue.offer(12);
        System.out.println(priorityQueue.peek());//12 小跟堆
    }
}
